// https://leetcode.cn/problems/soup-servings/
// Created by ade on 2022/11/21.
// 需要返回的值： 汤A 先分配完的概率 +  汤A和汤B 同时分配完的概率 / 2。返回值在正确答案 10-5 的范围内将被认为是正确的。
// 提供 100ml 的 汤A 和 0ml 的 汤B 。
// 提供 75ml 的 汤A 和 25ml 的 汤B 。
// 提供 50ml 的 汤A 和 50ml 的 汤B 。
// 提供 25ml 的 汤A 和 75ml 的 汤B 。
#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    /**
     * 思路：动态规划 dp[i][j] 代表剩下i个单位的A 和 j个单位的B的概率
     * dp[i][j] = (dp[i-4][j] + dp[i-3][j-1] + dp[i-2][j-2] + dp[i-3][j-1]) * 1/4;
     * 边界情况：
     * 当i>0 j=0 A不可能先分完， AB也不能同时分完 d[i][j] = 0;
     * 当i=0 j=0 A不可能先分完，AB能同时分完 dp[i][j] = 0 + 1*0.5
     * 当i=0 j>0 A先分完， AB不能同时分完 dp[i][j] = 1;
     *
     * @param n
     * @return
     */
    double soupServings(int n) {
        n = (n + 24) / 25;
        if (n > 179) return 1.0;
        vector <vector<float>> dp(n + 1, vector<float>(n + 1, 0.0));
        dp[0][0] = 0.5;
        for (int i = 1; i <= n; i++) {
            dp[0][i] = 1.0;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = (dp[max(0, i - 4)][j] + dp[max(0, i - 3)][max(0, j - 1)] +
                            dp[max(0, i - 2)][max(0, j - 2)] + dp[max(0, i - 1)][max(0, j - 3)]) / 4.0;
            }
        }
        return dp[n][n];
    }
};

int main() {
    Solution so;
    cout << so.soupServings(50) << endl;
    return 0;
}